home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 317 / asmsrc / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-20  |  30.7 KB  |  987 lines
  1. /* hash.c - hash table lookup strings - */
  2.  
  3. /* Copyright (C) 1987 Free Software Foundation, Inc.
  4.  
  5. This file is part of Gas, the GNU Assembler.
  6.  
  7. The GNU assembler is distributed in the hope that it will be
  8. useful, but WITHOUT ANY WARRANTY.  No author or distributor
  9. accepts responsibility to anyone for the consequences of using it
  10. or for whether it serves any particular purpose or works at all,
  11. unless he says so in writing.  Refer to the GNU Assembler General
  12. Public License for full details.
  13.  
  14. Everyone is granted permission to copy, modify and redistribute
  15. the GNU Assembler, but only under the conditions described in the
  16. GNU Assembler General Public License.  A copy of this license is
  17. supposed to have been given to you along with the GNU Assembler
  18. so you can know your rights and responsibilities.  It should be
  19. in a file named COPYING.  Among other things, the copyright
  20. notice and this notice must be preserved on all copies.  */
  21.  
  22. /*
  23.  * BUGS, GRIPES, APOLOGIA etc.
  24.  *
  25.  * A typical user doesn't need ALL this: I intend to make a library out
  26.  * of it one day - Dean Elsner.
  27.  * Also, I want to change the definition of a symbol to (address,length)
  28.  * so I can put arbitrary binary in the names stored. [see hsh.c for that]
  29.  *
  30.  * This slime is common coupled inside the module. Com-coupling (and other
  31.  * vandalism) was done to speed running time. The interfaces at the
  32.  * module's edges are adequately clean.
  33.  *
  34.  * There is no way to (a) run a test script through this heap and (b)
  35.  * compare results with previous scripts, to see if we have broken any
  36.  * code. Use GNU (f)utilities to do this. A few commands assist test.
  37.  * The testing is awkward: it tries to be both batch & interactive.
  38.  * For now, interactive rules!
  39.  */
  40.  
  41. /*
  42.  *  The idea is to implement a symbol table. A test jig is here.
  43.  *  Symbols are arbitrary strings; they can't contain '\0'.
  44.  *    [See hsh.c for a more general symbol flavour.]
  45.  *  Each symbol is associated with a char*, which can point to anything
  46.  *  you want, allowing an arbitrary property list for each symbol.
  47.  *
  48.  *  The basic operations are:
  49.  *
  50.  *    new                     creates symbol table, returns handle
  51.  *    find (symbol)           returns char*
  52.  *    insert (symbol,char*)   error if symbol already in table
  53.  *    delete (symbol)         returns char* if symbol was in table
  54.  *    apply                   so you can delete all symbols before die()
  55.  *    die                     destroy symbol table (free up memory)
  56.  *
  57.  *  Supplementary functions include:
  58.  *
  59.  *    say                     how big? what % full?
  60.  *    replace (symbol,newval) report previous value
  61.  *    jam (symbol,value)      assert symbol:=value
  62.  *
  63.  *  You, the caller, have control over errors: this just reports them.
  64.  *
  65.  *  This package requires malloc(), free().
  66.  *  Malloc(size) returns NULL or address of char[size].
  67.  *  Free(address) frees same.
  68.  */
  69.  
  70. /*
  71.  *  The code and its structures are re-enterent.
  72.  *  Before you do anything else, you must call hash_new() which will
  73.  *  return the address of a hash-table-control-block (or NULL if there
  74.  *  is not enough memory). You then use this address as a handle of the
  75.  *  symbol table by passing it to all the other hash_...() functions.
  76.  *  The only approved way to recover the memory used by the symbol table
  77.  *  is to call hash_die() with the handle of the symbol table.
  78.  *
  79.  *  Before you call hash_die() you normally delete anything pointed to
  80.  *  by individual symbols. After hash_die() you can't use that symbol
  81.  *  table again.
  82.  *
  83.  *  The char* you associate with a symbol may not be NULL (0) because
  84.  *  NULL is returned whenever a symbol is not in the table. Any other
  85.  *  value is OK, except DELETED, #defined below.
  86.  *
  87.  *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
  88.  *  STRING until that symbol is deleted from the table. The reason is that
  89.  *  only the address you supply, NOT the symbol string itself, is stored
  90.  *  in the symbol table.
  91.  *
  92.  *  You may delete and add symbols arbitrarily.
  93.  *  Any or all symbols may have the same 'value' (char *). In fact, these
  94.  *  routines don't do anything with your symbol values.
  95.  *
  96.  *  You have no right to know where the symbol:char* mapping is stored,
  97.  *  because it moves around in memory; also because we may change how it
  98.  *  works and we don't want to break your code do we? However the handle
  99.  *  (address of struct hash_control) is never changed in
  100.  *  the life of the symbol table.
  101.  *
  102.  *  What you CAN find out about a symbol table is:
  103.  *    how many slots are in the hash table?
  104.  *    how many slots are filled with symbols?
  105.  *    (total hashes,collisions) for (reads,writes) (*)
  106.  *  All of the above values vary in time.
  107.  *  (*) some of these numbers will not be meaningful if we change the
  108.  *  internals.
  109.  */
  110.  
  111. /*
  112.  *  I N T E R N A L
  113.  *
  114.  *  Hash table is an array of hash_entries; each entry is a pointer to a
  115.  *  a string and a user-supplied value 1 char* wide.
  116.  *
  117.  *  The array always has 2 ** n elements, n>0, n integer.
  118.  *  There is also a 'wall' entry after the array, which is always empty
  119.  *  and acts as a sentinel to stop running off the end of the array.
  120.  *  When the array gets too full, we create a new array twice as large
  121.  *  and re-hash the symbols into the new array, then forget the old array.
  122.  *  (Of course, we copy the values into the new array before we junk the
  123.  *  old array!)
  124.  *
  125.  */
  126.  
  127. #include <stdio.h>
  128. #define TRUE           (1)
  129. #define FALSE          (0)
  130. #include <ctype.h>
  131. #define min(a, b)    ((a) < (b) ? (a) : (b))
  132.  
  133. #include "hash.h"
  134. char *xmalloc();
  135.  
  136. #define DELETED     ((char *)1)    /* guarenteed invalid address */
  137. #define START_POWER    (11)    /* power of two: size of new hash table *//* JF was 6 */
  138. /* JF These next two aren't used any more. */
  139. /* #define START_SIZE    (64)    /* 2 ** START_POWER */
  140. /* #define START_FULL    (32)      /* number of entries before table expands */
  141. #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
  142.                 /* above TRUE if a symbol is in entry @ ptr */
  143.  
  144. #define STAT_SIZE      (0)      /* number of slots in hash table */
  145.                 /* the wall does not count here */
  146.                 /* we expect this is always a power of 2 */
  147. #define STAT_ACCESS    (1)    /* number of hash_ask()s */
  148. #define STAT__READ     (0)      /* reading */
  149. #define STAT__WRITE    (1)      /* writing */
  150. #define STAT_COLLIDE   (3)    /* number of collisions (total) */
  151.                 /* this may exceed STAT_ACCESS if we have */
  152.                 /* lots of collisions/access */
  153. #define STAT_USED      (5)    /* slots used right now */
  154. #define STATLENGTH     (6)    /* size of statistics block */
  155. #if STATLENGTH != HASH_STATLENGTH
  156. Panic! Please make #include "stat.h" agree with previous definitions!
  157. #endif
  158.  
  159. /* #define SUSPECT to do runtime checks */
  160. /* #define TEST to be a test jig for hash...() */
  161.  
  162. #ifdef TEST            /* TEST: use smaller hash table */
  163. #undef  START_POWER
  164. #define START_POWER (3)
  165. #undef  START_SIZE
  166. #define START_SIZE  (8)
  167. #undef  START_FULL
  168. #define START_FULL  (4)
  169. #endif
  170.  
  171. /*------------------ plan ---------------------------------- i = internal
  172.  
  173. struct hash_control * c;
  174. struct hash_entry   * e;                                                    i
  175. int                   b[z];     buffer for statistics
  176.                       z         size of b
  177. char                * s;        symbol string (address) [ key ]
  178. char                * v;        value string (address)  [datum]
  179. boolean               f;        TRUE if we found s in hash table            i
  180. char                * t;        error string; "" means OK
  181. int                   a;        access type [0...n)                         i
  182.  
  183. c=hash_new       ()             create new hash_control
  184.  
  185. hash_die         (c)            destroy hash_control (and hash table)
  186.                                 table should be empty.
  187.                                 doesn't check if table is empty.
  188.                                 c has no meaning after this.
  189.  
  190. hash_say         (c,b,z)        report statistics of hash_control.
  191.                                 also report number of available statistics.
  192.  
  193. v=hash_delete    (c,s)          delete symbol, return old value if any.
  194.     ask()                       NULL means no old value.
  195.     f
  196.  
  197. v=hash_replace   (c,s,v)        replace old value of s with v.
  198.     ask()                       NULL means no old value: no table change.
  199.     f
  200.  
  201. t=hash_insert    (c,s,v)        insert (s,v) in c.
  202.     ask()                       return error string.
  203.     f                           it is an error to insert if s is already
  204.                                 in table.
  205.                                 if any error, c is unchanged.
  206.  
  207. t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
  208.     ask()                       it may decide to GROW the table.            i
  209.     f                                                                       i
  210.     grow()                                                                  i
  211. t=hash_grow      (c)            grow the hash table.                        i
  212.     jam()                       will invoke JAM.                            i
  213.  
  214. ?=hash_apply     (c,y)          apply y() to every symbol in c.
  215.     y                           evtries visited in 'unspecified' order.
  216.  
  217. v=hash_find      (c,s)          return value of s, or NULL if s not in c.
  218.     ask()
  219.     f
  220.  
  221. f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
  222.     code()                      maintain collision stats in c.              i
  223.  
  224. .=hash_code      (c,s)          compute hash-code for s,                    i
  225.                                 from parameters of c.                       i
  226.  
  227. */
  228.  
  229. static char hash_found;        /* returned by hash_ask() to stop extra */
  230.                 /* testing. hash_ask() wants to return both */
  231.                 /* a slot and a status. This is the status. */
  232.                 /* TRUE: found symbol */
  233.                 /* FALSE: absent: empty or deleted slot */
  234.                 /* Also returned by hash_jam(). */
  235.                 /* TRUE: we replaced a value */
  236.                 /* FALSE: we inserted a value */
  237.  
  238. /*
  239.  *             h a s h _ n e w ( )
  240.  *
  241.  */
  242. struct hash_control *
  243. hash_new()            /* create a new hash table */
  244.                 /* return NULL if failed */
  245.                 /* return handle (address of struct hash) */
  246. {
  247.   register struct hash_control * retval;
  248.   register struct hash_entry *   room;    /* points  hash table *///
  249.   register struct hash_entry *   wall;
  250.   register struct hash_entry *   entry;
  251.   char *                malloc();
  252.   register int *                 ip;    /* scan stats block of struct hash_control */
  253.   register int *                 nd;    /* limit of stats block */
  254.  
  255.   if ( room = (struct hash_entry *) malloc( sizeof(struct hash_entry)*((1<<START_POWER) + 1) ) )
  256.                 /* +1 for the wall entry */
  257.     {
  258.       if ( retval = (struct hash_control *) malloc(sizeof(struct hash_control)) )
  259.     {
  260.       nd = retval->hash_stat + STATLENGTH;
  261.       for (ip=retval->hash_stat; ip<nd; ip++)
  262.         {
  263.           *ip = 0;
  264.         }
  265.  
  266.       retval -> hash_stat[STAT_SIZE]  = 1<<START_POWER;
  267.       retval -> hash_mask             = (1<<START_POWER) - 1;
  268.       retval -> hash_sizelog      = START_POWER;
  269.                 /* works for 1's compl ok */
  270.       retval -> hash_where            = room;
  271.       retval -> hash_wall             =
  272.         wall                          = room + (1<<START_POWER);
  273.       retval -> hash_full             = (1<<START_POWER)/2;
  274.       for (entry=room; entry<=wall; entry++)
  275.         {
  276.           entry->hash_string = NULL;
  277.         }
  278.     }
  279.     }
  280.   else
  281.     {
  282.       retval = NULL;        /* no room for table: fake a failure */
  283.     }
  284.   return(retval);        /* return NULL or set-up structs */
  285. }
  286.  
  287. /*
  288.  *           h a s h _ d i e ( )
  289.  *
  290.  * Table should be empty, but this is not checked.
  291.  * To empty the table, try hash_apply()ing a symbol deleter.
  292.  * Return to free memory both the hash table and it's control
  293.  * block.
  294.  * 'handle' has no meaning after this function.
  295.  * No errors are recoverable.
  296.  */
  297. void
  298. hash_die(handle)
  299.      struct hash_control * handle;
  300. {
  301.   free((char *)handle->hash_where);
  302.   free((char *)handle);
  303. }
  304.  
  305. /*
  306.  *           h a s h _ s a y ( )
  307.  *
  308.  * Return the size of the statistics table, and as many statistics as
  309.  * we can until either (a) we have run out of statistics or (b) caller
  310.  * has run out of buffer.
  311.  * NOTE: hash_say treats all statistics alike.
  312.  * These numbers may change with time, due to insertions, deletions
  313.  * and expansions of the table.
  314.  * The first "statistic" returned is the length of hash_stat[].
  315.  * Then contents of hash_stat[] are read out (in ascending order)
  316.  * until your buffer or hash_stat[] is exausted.
  317.  */
  318. void
  319. hash_say(handle,buffer,bufsiz)
  320.      register struct hash_control * handle;
  321.      register int                   buffer[/*bufsiz*/];
  322.      register int                   bufsiz;
  323. {
  324.   register int * nd;            /* limit of statistics block */
  325.   register int * ip;            /* scan statistics */
  326.  
  327.   ip = handle -> hash_stat;
  328.   nd = ip + min(bufsiz-1,STATLENGTH);
  329.   if (bufsiz>0)            /* trust nothing! bufsiz<=0 is dangerous */
  330.     {
  331.       *buffer++ = STATLENGTH;
  332.       for (; ip<nd; ip++,buffer++)
  333.     {
  334.       *buffer = *ip;
  335.     }
  336.     }
  337. }
  338.  
  339. /*
  340.  *           h a s h _ d e l e t e ( )
  341.  *
  342.  * Try to delete a symbol from the table.
  343.  * If it was there, return its value (and adjust STAT_USED).
  344.  * Otherwise, return NULL.
  345.  * Anyway, the symbol is not present after this function.
  346.  *
  347.  */
  348. char *                /* NULL if string not in table, else */
  349.                 /* returns value of deleted symbol */
  350. hash_delete(handle,string)
  351.      register struct hash_control * handle;
  352.      register char *                string;
  353. {
  354.   register char *                   retval; /* NULL if string not in table */
  355.   register struct hash_entry *      entry; /* NULL or entry of this symbol */
  356.   struct hash_entry * hash_ask();
  357.  
  358.   entry = hash_ask(handle,string,STAT__WRITE);
  359.   if (hash_found)
  360.     {
  361.       retval = entry -> hash_value;
  362.       entry -> hash_string = DELETED; /* mark as deleted */
  363.       handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */
  364. #ifdef SUSPECT
  365.       if (handle->hash_stat[STAT_USED]<0)
  366.         {
  367.           error("hash_delete");
  368.         }
  369. #endif def SUSPECT
  370.     }
  371.   else
  372.     {
  373.       retval = NULL;
  374.     }
  375.   return(retval);
  376. }
  377.  
  378. /*
  379.  *                   h a s h _ r e p l a c e ( )
  380.  *
  381.  * Try to replace the old value of a symbol with a new value.
  382.  * Normally return the old value.
  383.  * Return NULL and don't change the table if the symbol is not already
  384.  * in the table.
  385.  */
  386. char *
  387. hash_replace(handle,string,value)
  388.      register struct hash_control * handle;
  389.      register char *                string;
  390.      register char *                value;
  391. {
  392.   register struct hash_entry *      entry;
  393.   register char *                   retval;
  394.   struct hash_entry * hash_ask();
  395.  
  396.   entry = hash_ask(handle,string,STAT__WRITE);
  397.   if (hash_found)
  398.     {
  399.       retval = entry -> hash_value;
  400.       entry -> hash_value = value;
  401.     }
  402.   else
  403.     {
  404.       retval = NULL;
  405.     }
  406.   ;
  407.   return (retval);
  408. }
  409.  
  410. /*
  411.  *                   h a s h _ i n s e r t ( )
  412.  *
  413.  * Insert a (symbol-string, value) into the hash table.
  414.  * Return an error string, "" means OK.
  415.  * It is an 'error' to insert an existing symbol.
  416.  */
  417.  
  418. char *                /* return error string */
  419. hash_insert(handle,string,value)
  420.      register struct hash_control * handle;
  421.      register char *                string;
  422.      register char *                value;
  423. {
  424.   register struct hash_entry * entry;
  425.   register char *              retval;
  426.   char * hash_grow();
  427.   struct hash_entry * hash_ask();
  428.  
  429.   retval = "";
  430.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  431.     {
  432.       retval = hash_grow(handle);
  433.     }
  434.   if ( ! * retval)
  435.     {
  436.       entry = hash_ask(handle,string,STAT__WRITE);
  437.       if (hash_found)
  438.     {
  439.       retval = "exists";
  440.     }
  441.       else
  442.     {
  443.       entry -> hash_value  = value;
  444.       entry -> hash_string = string;
  445.       handle-> hash_stat[STAT_USED]  += 1;
  446.     }
  447.     }
  448.   return(retval);
  449. }
  450.  
  451. /*
  452.  *               h a s h _ j a m ( )
  453.  *
  454.  * Regardless of what was in the symbol table before, after hash_jam()
  455.  * the named symbol has the given value. The symbol is either inserted or
  456.  * (its value is) relpaced.
  457.  * An error message string is returned, "" means OK.
  458.  *
  459.  * WARNING: this may decide to grow the hashed symbol table.
  460.  * To do this, we call hash_grow(), WHICH WILL recursively CALL US.
  461.  *
  462.  * We report status internally: hash_found is TRUE if we replaced, but
  463.  * false if we inserted.
  464.  */
  465. char *
  466. hash_jam(handle,string,value)
  467.      register struct hash_control * handle;
  468.      register char *                string;
  469.      register char *                value;
  470. {
  471.   register char *                   retval;
  472.   char * hash_grow();
  473.   register struct hash_entry *      entry;
  474.   struct hash_entry * hash_ask();
  475.  
  476.   retval = "";
  477.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  478.     {
  479.       retval = hash_grow(handle);
  480.     }
  481.   if (! * retval)
  482.     {
  483.       entry = hash_ask(handle,string,STAT__WRITE);
  484.       if ( ! hash_found)
  485.     {
  486.       entry -> hash_string = string;
  487.       handle->hash_stat[STAT_USED] += 1;
  488.     }
  489.       entry -> hash_value = value;
  490.     }
  491.   return(retval);
  492. }
  493.  
  494. /*
  495.  *               h a s h _ g r o w ( )
  496.  *
  497.  * Grow a new (bigger) hash table from the old one.
  498.  * We choose to double the hash table's size.
  499.  * Return a human-scrutible error string: "" if OK.
  500.  * Warning! This uses hash_jam(), which had better not recurse
  501.  * back here! Hash_jam() conditionally calls us, but we ALWAYS
  502.  * call hash_jam()!
  503.  * Internal.
  504.  */
  505. static char *
  506. hash_grow(handle)            /* make a hash table grow */
  507.      struct hash_control * handle;
  508. {
  509.   register struct hash_entry *      newwall;
  510.   register struct hash_entry *      newwhere;
  511.   struct hash_entry *      newtrack;
  512.   register struct hash_entry *      oldtrack;
  513.   register struct hash_entry *      oldwhere;
  514.   register struct hash_entry *      oldwall;
  515.   register int                      temp;
  516.   int                      newsize;
  517.   char *                   string;
  518.   char *                   retval;
  519. #ifdef SUSPECT
  520.   int                      oldused;
  521. #endif
  522.  
  523.   /*
  524.    * capture info about old hash table
  525.    */
  526.   oldwhere = handle -> hash_where;
  527.   oldwall  = handle -> hash_wall;
  528. #ifdef SUSPECT
  529.   oldused  = handle -> hash_stat[STAT_USED];
  530. #endif
  531.   /*
  532.    * attempt to get enough room for a hash table twice as big
  533.    */
  534.   temp = handle->hash_stat[STAT_SIZE];
  535.   if ( newwhere = (struct hash_entry *) xmalloc((long)((temp+temp+1)*sizeof(struct hash_entry))))
  536.                 /* +1 for wall slot */
  537.     {
  538.       retval = "";        /* assume success until proven otherwise */
  539.       /*
  540.        * have enough room: now we do all the work.
  541.        * double the size of everything in handle,
  542.        * note: hash_mask frob works for 1's & for 2's complement machines
  543.        */
  544.       handle->hash_mask              = handle->hash_mask + handle->hash_mask + 1;
  545.       newsize                        =
  546.       handle->hash_stat[STAT_SIZE] <<= 1;
  547.       handle->hash_where             = newwhere;
  548.       handle->hash_full            <<= 1;
  549.       handle->hash_sizelog        += 1;
  550.       handle->hash_stat[STAT_USED]   = 0;
  551.       handle->hash_wall              =
  552.       newwall                        = newwhere + newsize;
  553.       /*
  554.        * set all those pesky new slots to vacant.
  555.        */
  556.       for (newtrack=newwhere; newtrack < newwall; newtrack++)
  557.     {
  558.       newtrack -> hash_string = NULL;
  559.     }
  560.       /*
  561.        * we will do a scan of the old table, the hard way, using the
  562.        * new control block to re-insert the data into new hash table.
  563.        */
  564.       handle -> hash_stat[STAT_USED] = 0;    /* inserts will bump it up to correct */
  565.       for (oldtrack=oldwhere; oldtrack < oldwall; oldtrack++)
  566.     {
  567.       if ( (string=oldtrack->hash_string) && string!=DELETED )
  568.         {
  569.           if ( * (retval = hash_jam(handle,string,oldtrack->hash_value) ) )
  570.         {
  571.           break;
  572.         }
  573.         }
  574.     }
  575. #ifdef SUSPECT
  576.       if ( !*retval && handle->hash_stat[STAT_USED] != oldused)
  577.     {
  578.       retval = "hash_used";
  579.     }
  580. #endif
  581.       if (!*retval)
  582.     {
  583.       /*
  584.        * we have a completely faked up control block.
  585.        * return the old hash table.
  586.        */
  587.       free((char *)oldwhere);
  588.       /*
  589.        * Here with success. retval is already "".
  590.        */
  591.     }
  592.     }
  593.   else
  594.     {
  595.       retval = "no room";
  596.     }
  597.   return(retval);
  598. }
  599.  
  600. /*
  601.  *          h a s h _ a p p l y ( )
  602.  *
  603.  * Use this to scan each entry in symbol table.
  604.  * For each symbol, this calls (applys) a nominated function supplying the
  605.  * symbol's value (and the symbol's name).
  606.  * The idea is you use this to destroy whatever is associted with
  607.  * any values in the table BEFORE you destroy the table with hash_die.
  608.  * Of course, you can use it for other jobs; whenever you need to
  609.  * visit all extant symbols in the table.
  610.  *
  611.  * We choose to have a call-you-back idea for two reasons:
  612.  *  asthetic: it is a neater idea to use apply than an explicit loop
  613.  *  sensible: if we ever had to grow the symbol table (due to insertions)
  614.  *            then we would lose our place in the table when we re-hashed
  615.  *            symbols into the new table in a different order.
  616.  *
  617.  * The order symbols are visited depends entirely on the hashing function.
  618.  * Whenever you insert a (symbol, value) you risk expanding the table. If
  619.  * you do expand the table, then the hashing function WILL change, so you
  620.  * MIGHT get a different order of symbols visited. In other words, if you
  621.  * want the same order of visiting symbols as the last time you used
  622.  * hash_apply() then you better not have done any hash_insert()s or
  623.  * hash_jam()s since the last time you used hash_apply().
  624.  *
  625.  * In future we may use the value returned by your nominated function.
  626.  * One idea is to abort the scan if, after applying the function to a
  627.  * certain node, the function returns a certain code.
  628.  * To be safe, please make your functions of type char *. If you always
  629.  * return NULL, then the scan will complete, visiting every symbol in
  630.  * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
  631.  * Caveat Actor!
  632.  *
  633.  * The function you supply should be of the form:
  634.  *      char * myfunct(string,value)
  635.  *              char * string;        |* the symbol's name *|
  636.  *              char * value;         |* the symbol's value *|
  637.  *      {
  638.  *        |* ... *|
  639.  *        return(NULL);
  640.  *      }
  641.  *
  642.  * The returned value of hash_apply() is (char*)NULL. In future it may return
  643.  * other values. NULL means "completed scan OK". Other values have no meaning
  644.  * yet. (The function has no graceful failures.)
  645.  */
  646. char *
  647. hash_apply(handle,function)
  648.      struct hash_control * handle;
  649.      char*                 (*function)();
  650. {
  651.   register struct hash_entry *      entry;
  652.   register struct hash_entry *      wall;
  653.  
  654.   wall = handle->hash_wall;
  655.   for (entry = handle->hash_where; entry < wall; entry++)
  656.     {
  657.       if (islive(entry))    /* silly code: tests entry->string twice! */
  658.     {
  659.       (*function)(entry->hash_string,entry->hash_value);
  660.     }
  661.     }
  662.   return (NULL);
  663. }
  664.  
  665. /*
  666.  *          h a s h _ f i n d ( )
  667.  *
  668.  * Given symbol string, find value (if any).
  669.  * Return found value or NULL.
  670.  */
  671. char *
  672. hash_find(handle,string)    /* return char* or NULL */
  673.      struct hash_control * handle;
  674.      char *                string;
  675. {
  676.   register struct hash_entry *      entry;
  677.   register char *                   retval;
  678.   struct hash_entry *      hash_ask();
  679.  
  680.   entry = hash_ask(handle,string,STAT__READ);
  681.   if (hash_found)
  682.     {
  683.       retval = entry->hash_value;
  684.     }
  685.   else
  686.     {
  687.       retval = NULL;
  688.     }
  689.   return(retval);
  690. }
  691.  
  692. /*
  693.  *          h a s h _ a s k ( )
  694.  *
  695.  * Searches for given symbol string.
  696.  * Return the slot where it OUGHT to live. It may be there.
  697.  * Return hash_found: TRUE only if symbol is in that slot.
  698.  * Access argument is to help keep statistics in control block.
  699.  * Internal.
  700.  */
  701. static struct hash_entry *    /* string slot, may be empty or deleted */
  702. hash_ask(handle,string,access)
  703.      struct hash_control * handle;
  704.      char *                string;
  705.      int                   access; /* access type */
  706. {
  707.   register char    *string1;    /* JF avoid strcmp calls */
  708.   register char *                   s;
  709.   register int                      c;
  710.   register struct hash_entry *      slot;
  711.   register int                      collision; /* count collisions */
  712.  
  713.   slot = handle->hash_where + hash_code(handle,string); /* start looking here */
  714.   handle->hash_stat[STAT_ACCESS+access] += 1;
  715.   collision = 0;
  716.   hash_found = FALSE;
  717.   while ( (s = slot->hash_string) && s!=DELETED )
  718.     {
  719.         for(string1=string;;) {
  720.         if(!(c= *s++)) {
  721.             if(!*string1)
  722.                 hash_found = TRUE;
  723.             break;
  724.         }
  725.         if(*string1++!=c)
  726.             break;
  727.     }
  728.     if(hash_found)
  729.         break;
  730.       collision++;
  731.       slot++;
  732.     }
  733.   /*
  734.    * slot:                                                      return:
  735.    *       in use:     we found string                           slot
  736.    *       at empty:
  737.    *                   at wall:        we fell off: wrap round   ????
  738.    *                   in table:       dig here                  slot
  739.    *       at DELETED: dig here                                  slot
  740.    */
  741.   if (slot==handle->hash_wall)
  742.     {
  743.       slot = handle->hash_where; /* now look again */
  744.       while( (s = slot->hash_string) && s!=DELETED )
  745.     {
  746.       for(string1=string;*s;string1++,s++) {
  747.         if(*string1!=*s)
  748.         break;
  749.       }
  750.       if(*s==*string1) {
  751.           hash_found = TRUE;
  752.           break;
  753.         }
  754.       collision++;
  755.       slot++;
  756.     }
  757.       /*
  758.        * slot:                                                   return:
  759.        *       in use: we found it                                slot
  760.        *       empty:  wall:         ERROR IMPOSSIBLE             !!!!
  761.        *               in table:     dig here                     slot
  762.        *       DELETED:dig here                                   slot
  763.        */
  764.     }
  765. /*   fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */
  766.   handle -> hash_stat[STAT_COLLIDE+access] += collision;
  767.   return(slot);            /* also return hash_found */
  768. }
  769.  
  770. /*
  771.  *           h a s h _ c o d e
  772.  *
  773.  * Does hashing of symbol string to hash number.
  774.  * Internal.
  775.  */
  776. static int
  777. hash_code(handle,string)
  778.      struct hash_control * handle;
  779.      register char *                string;
  780. {
  781.   register long int                 h;      /* hash code built here */
  782.   register long int                 c;      /* each character lands here */
  783.   register int               n;      /* Amount to shift h by */
  784.  
  785.   n = (handle->hash_sizelog - 3);
  786.   h = 0;
  787.   while (c = *string++)
  788.     {
  789.       h += c;
  790.       h = (h<<3) + (h>>n) + c;
  791.     }
  792.   return (h & handle->hash_mask);
  793. }
  794.  
  795. /*
  796.  * Here is a test program to exercise above.
  797.  */
  798. #ifdef TEST
  799.  
  800. #define TABLES (6)        /* number of hash tables to maintain */
  801.                 /* (at once) in any testing */
  802. #define STATBUFSIZE (12)    /* we can have 12 statistics */
  803.  
  804. int statbuf[STATBUFSIZE];    /* display statistics here */
  805. char answer[100];        /* human farts here */
  806. char * hashtable[TABLES];    /* we test many hash tables at once */
  807. char * h;            /* points to curent hash_control */
  808. char ** pp;
  809. char *  p;
  810. char *  name;
  811. char *  value;
  812. int     size;
  813. int     used;
  814. char    command;
  815. int     number;            /* number 0:TABLES-1 of current hashed */
  816.                 /* symbol table */
  817.  
  818. main()
  819. {
  820.   char (*applicatee());
  821.   char * hash_find();
  822.   char * destroy();
  823.   char * what();
  824.   struct hash_control * hash_new();
  825.   char * hash_replace();
  826.   int *  ip;
  827.  
  828.   number = 0;
  829.   h = 0;
  830.   printf("type h <RETURN> for help\n");
  831.   for(;;)
  832.     {
  833.       printf("hash_test command: ");
  834.       gets(answer);
  835.       command = answer[0];
  836.       if (isupper(command)) command = tolower(command);    /* ecch! */
  837.       switch (command)
  838.     {
  839.     case '#':
  840.       printf("old hash table #=%d.\n",number);
  841.       whattable();
  842.       break;
  843.     case '?':
  844.       for (pp=hashtable; pp<hashtable+TABLES; pp++)
  845.         {
  846.           printf("address of hash table #%d control block is %xx\n"
  847.              ,pp-hashtable,*pp);
  848.         }
  849.       break;
  850.     case 'a':
  851.       hash_apply(h,applicatee);
  852.       break;
  853.     case 'd':
  854.       hash_apply(h,destroy);
  855.       hash_die(h);
  856.       break;
  857.     case 'f':
  858.       p = hash_find(h,name=what("symbol"));
  859.       printf("value of \"%s\" is \"%s\"\n",name,p?p:"NOT-PRESENT");
  860.       break;
  861.     case 'h':
  862.       printf("# show old, select new default hash table number\n");
  863.       printf("? display all hashtable control block addresses\n");
  864.       printf("a apply a simple display-er to each symbol in table\n");
  865.       printf("d die: destroy hashtable\n");
  866.       printf("f find value of nominated symbol\n");
  867.       printf("h this help\n");
  868.       printf("i insert value into symbol\n");
  869.       printf("j jam value into symbol\n");
  870.       printf("n new hashtable\n");
  871.       printf("r replace a value with another\n");
  872.       printf("s say what %% of table is used\n");
  873.       printf("q exit this program\n");
  874.       printf("x delete a symbol from table, report its value\n");
  875.       break;
  876.     case 'i':
  877.       p = hash_insert(h,name=what("symbol"),value=what("value"));
  878.       if (*p)
  879.         {
  880.           printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,p);
  881.         }
  882.       break;
  883.     case 'j':
  884.       p = hash_jam(h,name=what("symbol"),value=what("value"));
  885.       if (*p)
  886.         {
  887.           printf("symbol=\"%s\"  value=\"%s\"  error=%s\n",name,value,p);
  888.         }
  889.       break;
  890.     case 'n':
  891.       h = hashtable[number] = (char *) hash_new();
  892.       break;
  893.     case 'q':
  894.       exit();
  895.     case 'r':
  896.       p = hash_replace(h,name=what("symbol"),value=what("value"));
  897.       printf("old value was \"%s\"\n",p?p:"{}");
  898.       break;
  899.     case 's':
  900.       hash_say(h,statbuf,STATBUFSIZE);
  901.       for (ip=statbuf; ip<statbuf+STATBUFSIZE; ip++)
  902.         {
  903.           printf("%d ",*ip);
  904.         }
  905.       printf("\n");
  906.       break;
  907.     case 'x':
  908.       p = hash_delete(h,name=what("symbol"));
  909.       printf("old value was \"%s\"\n",p?p:"{}");
  910.       break;
  911.     default:
  912.       printf("I can't understand command \"%c\"\n",command);
  913.       break;
  914.     }
  915.     }
  916. }
  917.  
  918. char *
  919. what(description)
  920.      char * description;
  921. {
  922.   char * retval;
  923.   char * malloc();
  924.  
  925.   printf("   %s : ",description);
  926.   gets(answer);
  927.   /* will one day clean up answer here */
  928.   retval = malloc(strlen(answer)+1);
  929.   if (!retval)
  930.     {
  931.       error("room");
  932.     }
  933.   (void)strcpy(retval,answer);
  934.   return(retval);
  935. }
  936.  
  937. char *
  938. destroy(string,value)
  939.      char * string;
  940.      char * value;
  941. {
  942.   free(string);
  943.   free(value);
  944.   return(NULL);
  945. }
  946.  
  947.  
  948. char *
  949. applicatee(string,value)
  950.      char * string;
  951.      char * value;
  952. {
  953.   printf("%.20s-%.20s\n",string,value);
  954.   return(NULL);
  955. }
  956.  
  957. whattable()            /* determine number: what hash table to use */
  958.                 /* also determine h: points to hash_control */
  959. {
  960.  
  961.   for (;;)
  962.     {
  963.       printf("   what hash table (%d:%d) ?  ",0,TABLES-1);
  964.       gets(answer);
  965.       sscanf(answer,"%d",&number);
  966.       if (number>=0 && number<TABLES)
  967.     {
  968.       h = hashtable[number];
  969.       if (!h)
  970.         {
  971.           printf("warning: current hash-table-#%d. has no hash-control\n",number);
  972.         }
  973.       return;
  974.     }
  975.       else
  976.     {
  977.       printf("invalid hash table number: %d\n",number);
  978.     }
  979.     }
  980. }
  981.  
  982.  
  983.  
  984. #endif /* #ifdef TEST */
  985.  
  986. /* end: hash.c */
  987.